我们可以思考一下如何用求两个串的最长公共子串点这里。
多个字符串匹配也很简单,对于每个节点记录每个字符串能匹配的最大值的最小值。
求最大值就是求两个串的最长公共子串,只不过需要给父节点更新,每次取最小值就得到答案。
只不过为了保证先更新儿子,再更新父亲,我们需要用拓扑序实现。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN = 2 * 100000 , MAXC = 26;
struct Suffix_Automaton {
int Size , Last , Root , Maxlen[ MAXN + 5 ];
int Trans[ MAXN + 5 ][ MAXC + 5 ] , Link[ MAXN + 5 ];
int Max[ MAXN + 5 ] , Min[ MAXN + 5 ];
int Sortlen[ MAXN + 5 ] , tot[ MAXN + 5 ];
Suffix_Automaton( ) { Root = Size = Last = 1; }
void Copy( int u , int v ) {
for( int i = 1 ; i <= MAXC ; i ++ )
Trans[ u ][ i ] = Trans[ v ][ i ];
}
void Extend( int chr ) {
int Newnode = ++ Size , u = Last;
Maxlen[ Newnode ] = Maxlen[ u ] + 1;
for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
Trans[ u ][ chr ] = Newnode;
if( !u ) Link[ Newnode ] = Root;
else {
int v = Trans[ u ][ chr ];
if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
else {
int w = ++ Size;
Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
Link[ w ] = Link[ v ];
Link[ v ] = Link[ Newnode ] = w;
}
}
Last = Newnode;
}
void Sort( ) {
for( int i = 1 ; i <= Size ; i ++ ) tot[ Maxlen[ i ] ] ++;
for( int i = 1 ; i <= Size ; i ++ ) tot[ i ] += tot[ i - 1 ];
for( int i = 1 ; i <= Size ; i ++ ) Sortlen[ tot[ Maxlen[ i ] ] -- ] = i;
}
void Build( char *str ) {
int len = strlen( str );
for( int i = 0 ; i < len ; i ++ )
Extend( str[ i ] - 'a' + 1 );
Sort( );
for( int i = 1 ; i <= Size ; i ++ ) Min[ i ] = INF;
}
void Work( char *str ) {
int len = strlen( str );
int u = Root , cnt = 0;
for( int i = 0 ; i < len ; i ++ ) {
int ch = str[ i ] - 'a' + 1;
for( ; u && !Trans[ u ][ ch ] ; u = Link[ u ] ) cnt = Maxlen[ Link[ u ] ];
if( u ) {
u = Trans[ u ][ ch ];
Max[ u ] = max( Max[ u ] , ++ cnt );
}
else
u = Root , cnt = 0;
}
for( int i = Size ; i >= 1 ; i -- ) {
int u = Sortlen[ i ] , Fa = Link[ u ];
Max[ Fa ] = max( Max[ Fa ] , min( Maxlen[ Fa ] , Max[ u ] ) );
Min[ u ] = min( Min[ u ] , Max[ u ] ); Max[ u ] = 0;
}
}
}SAM;
int n , Ans;
char str[ 11 ][ MAXN + 5 ];
int main( ) {
for( n = 1 ; ~scanf("%s",str[ n ]) ; n ++ ); n --;
SAM.Build( str[ 1 ] );
for( int i = 2 ; i <= n ; i ++ ) SAM.Work( str[ i ] );
for( int i = 1 ; i <= SAM.Size ; i ++ )
Ans = max( Ans , SAM.Min[ i ] );
printf("%d",Ans);
return 0;
}